using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using ProtoBuf;

namespace GeoAzure.Core
{
    [Serializable]
    [ProtoContract]
    public class RTree<T> : ITreeNodeParent<T> where T : class
    {

        #region Member variables

        [ProtoMember(1)]
        private IndexEntry<T> _rootEntry;

        [ProtoMember(2)]
        private int _depth = 1;

        /// <summary>
        /// The Logical Sequence Number for nodes
        /// </summary>
        private long _nextLsn = 1;

        private readonly Searcher<T> _searcher = new Searcher<T>();

        #endregion

        public RTree()
        {
            var rootNode = new TreeNode<T>(0, GetNewLsn());
            rootNode.LockForReading();
            RootEntry = new IndexEntry<T>(rootNode);
            rootNode.ReleaseReadLock();
        }

        [ProtoAfterDeserialization]
        private void AfterDeserialization()
        {
            //RootEntry.Node.Parent = this;
        }

        /// <summary>
        /// This method is called when the root node was split, asking for an update of the index itself, by
        /// creating a new root node.
        /// </summary>
        /// <param name="splitEntry">The sibling entry to the old root. The old root entry must still be updated at this stage.</param>
        internal void SplitRootNode(IndexEntry<T> splitEntry)
        {
            // Here we simply increment the depth of the tree
            // TODO: potential concurrency issue here, when several inserters
            // cause a simultaneous split of the root
            var newRoot = new TreeNode<T>(_depth, GetNewLsn());
            newRoot.LockForWriting();
            _depth++;

            // update our old root entry with the bounds and LSN that were
            // updated due to the split. We update before adding the entry to the new root
            RootEntry.Update();
            // add the two entries to the new root
            
            newRoot.AddEntry(RootEntry);
            newRoot.AddEntry(splitEntry);
            RootEntry = new IndexEntry<T>(newRoot);
            newRoot.ReleaseWriteLock();
        }

        public void InsertItem(T item, GeoRectangle bounds)
        {
            var newEntry = new IndexEntry<T>(item, bounds);

            new Inserter<T>().Insert(new InsertionContext<T>(newEntry, 0, this));
        }

        public bool DeleteItem(T item, GeoRectangle bounds)
        {
            IndexEntry<T> entryToDelete = null;
            // TODO: implement deletion
            //entryToDelete = FindEntry(item, bounds);
            return ((ITreeNodeParent<T>) this).Delete(new DeletionContext<T>(entryToDelete, 0));
        }

        void ITreeNodeParent<T>.Insert(InsertionContext<T> context)
        {
            // we are being asked to insert at this level
            if (context.TargetLevel == Level)
            {
                // Here we simply increment the depth of the tree
                // The given node will become a child of the new root
                var newRoot = new TreeNode<T>(_depth, GetNewLsn());
                _depth++;
                newRoot.Insert(context);
                // TODO: lock _rootEntry for reading
                newRoot.Insert(new InsertionContext<T>(RootEntry, context.TargetLevel, this));
                //_rootEntry = new IndexEntry<T>(newRoot, GeoRectangle.CreateMinimumBoundingRectangle(newRoot.Entries));
            }
            else
            {
                Debug.Assert(context.TargetLevel < Level);
                RootEntry.Node.Insert(context);
            }
        }

        bool ITreeNodeParent<T>.Delete(DeletionContext<T> context)
        {
            // we are being asked to delete at this level
            // that means that the root has a single child
            if (context.TargetLevel == Level)
            {
                Debug.Assert(context.Entry == RootEntry);
                Debug.Assert(!RootEntry.Node.IsLeaf);
                Debug.Assert(RootEntry.Node.Entries.Count == 1);
                // Here we simply decrement the depth of the tree
                _depth--;
                // and we have a new root
                RootEntry = RootEntry.Node.Entries[0];
                //RootEntry.Node.Parent = this;
                return true;
            }
            else
            {
                // we are being asked to delete an element from the tree
                Debug.Assert(context.TargetLevel < Level);
                if (RootEntry.Node.Delete(context))  // element was found and deleted
                {
                    // now reinsert orphaned entries
                    for (int i = 0; i < context.DeletedNodes.Count; i++)
                    {
                        var deletedNode = context.DeletedNodes[i];
                        for (int j = 0; j < deletedNode.Entries.Count; j++)
                            ((ITreeNodeParent<T>) this).Insert(new InsertionContext<T>(deletedNode.Entries[j], deletedNode.Level, this));
                    }
                    return true;
                }
            }
            return false;
        }

        void ITreeNodeParent<T>.ReadjustBounds()
        {
            // nothing to do in our case
        }

        internal long GetNewLsn()
        {
            return Interlocked.Increment(ref _nextLsn);
        }

        public int Level
        {
            get { return _depth; }
        }

        public int Count
        {
            get
            {
                int result = 0;
                RootEntry.Node.CountElementsInLeaves(ref result);
                return result;
            }
        }

        public int NodeCount
        {
            get
            {
                // we will count the nodes at each level
                int[] results = new int[_depth];
                results[RootEntry.Node.Level] = 1;
                RootEntry.Node.CountNodes(results);

                return results.Sum();
            }
        }

        internal IndexEntry<T> RootEntry
        {
            get { return _rootEntry; }
            set { _rootEntry = value; }
        }

        public IEnumerable<T> Query(GeoRectangle queryRectangle)
        {
            return _searcher.Query(_rootEntry, queryRectangle);
        }

        public IEnumerable<T> QueryWithinDistance(Location centerLocation, double distance)
        {
            return _searcher.QueryWithinDistance(_rootEntry, centerLocation, distance);
        }
    }
}